package bintree.leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树最大宽度
 * @author yuisama
 * @date 2022/01/13 18:14
 **/
public class Num662 {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int max = 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> ret = new ArrayList<>();
        while (!queue.isEmpty()) {
            // 当前层的节点个数
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                if (queue.peekFirst() == null && queue.peekLast() == null) {
                    // 空层，清空队列，直接退出。
                    queue.clear();
                    break;
                }else {
                    TreeNode node = queue.poll();
                    // 处理空节点的情况
                    if (node == null) {
                        temp.add(null);
                        // 再向队列中添加两个null
                        queue.add(null);
                        queue.add(null);
                    }else {
                        temp.add(node.val);
                        // 叶子节点直接跳过
                        if (node.left != null || node.right != null) {
                            queue.add(node.left);
                            queue.add(node.right);
                        }
                    }
                }
            }
            if (temp.size() != 0) {
                ret.add(temp);
            }
        }
        System.out.println();
        // 遍历ret集合，取出每一行数据，找最大宽度
        for (int i = 0; i < ret.size(); i++) {
            int tempSize = 0;
            List<Integer> temp = ret.get(i);
            if (temp.get(temp.size() - 1) == null) {
                tempSize = 1;
            }else {
                tempSize = temp.size();
            }
            max = Math.max(max,tempSize);
        }
        return max;
    }

    public static void main(String[] args) {
        Num662 solution = new Num662();
        int max = solution.widthOfBinaryTree(build());
        System.out.println(max);
    }

    public static TreeNode build() {
        TreeNode root = new TreeNode(1);
        TreeNode r1 = new TreeNode(3);
        TreeNode r2 = new TreeNode(2);
        root.left = r1;
        root.right = r2;
        TreeNode r3 = new TreeNode(5);
        TreeNode r4 = new TreeNode(9);
        r1.left = r3;
        r1.right = null;
        r2.left = null;
        r2.right = r4;
        TreeNode r5 = new TreeNode(6);
        TreeNode r6 = new TreeNode(7);
        r3.left = r5;
        r3.right = null;
        r4.left = null;
        r4.right = r6;
        return root;
    }
}